package com.zyk.grate_offer.class05;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？
 * 比如 s1 = "abcde"，s2 = "axbc"
 *
 * @author zhangsan
 * @date 2021/5/6 16:47
 */
public class Code03_MinimumNumberOfDelete {

    // 1: 讲生成str2的所有子序列, 对str1.进行KMP(indexOf). 子序列由长往短比
    // 时间复杂度: O(N * 2^M)
    // 适合str2不长的情况下使用
    public static int minCost1(String s1, String s2) {
        List<String> s2Subs = new ArrayList<>();
        process(s2.toCharArray(), 0, "", s2Subs);
        s2Subs.sort((o1, o2) -> o2.length() - o1.length());
        for (String str : s2Subs) {
            if (s1.indexOf(str) != -1) { // indexOf底层和KMP算法代价几乎一样，也可以用KMP代替
                return s2.length() - str.length();
            }
        }
        return s2.length();
    }

    public static void process(char[] str2, int index, String path, List<String> list) {
        if (index == str2.length) {
            list.add(path);
            return;
        }
        process(str2, index + 1, path, list);
        process(str2, index + 1, path + str2[index], list);
    }


    // 2: 编辑酒距离变种(只能删除).对str1的所有子串和str2进行编辑距离问题.
    // 时间复杂度: O(N^3 * M)
    // 如果str2长选用这种算法
    public static int minCost2(String str1, String str2) {
        // str1的全部子串.
        int N = str1.length();
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int len = 1; len <= N - i; len++) {
//                ans = Math.min(ans, delDistance(str2.toCharArray(), str1.substring(i, i + len).toCharArray()));
                ans = Math.min(ans, onlyDelete(str2.toCharArray(), str1.substring(i, i + len).toCharArray()));
            }
        }
        return ans == Integer.MAX_VALUE ? str2.length() : ans;
    }

    // s1 => s2, 最短消耗
    // 可使用空间压缩, 改成 1维数组. 且使用全局的一个dp数组省空间. 这里只考虑时间复杂度就先不改
    public static int delDistance(char[] s1, char[] s2) {
        if (s1.length < s2.length) return Integer.MAX_VALUE;
        int R = s1.length + 1;
        int C = s2.length + 1;
        int[][] dp = new int[R][C];
        for (int r = 0; r < R; r++) {   // (00 11 22那条线) 右上边填无效值
            for (int c = r + 1; c < C; c++) {
                dp[r][c] = Integer.MAX_VALUE;
            }
        }
        for (int r = 1; r < R; r++) {   // 0,0  1,1, 2,2  n,n 这条线上边不填因为涉及添加
            dp[r][0] = r;
        }
        for (int r = 1; r < R; r++) {
            int range = Math.min(C, r + 1);     // <= Math.min(C-1, r)
            for (int c = 1; c < range; c++) {
//                dp[r][c] = Integer.MAX_VALUE;
                if (dp[r - 1][c] != Integer.MAX_VALUE) {   // 如果我前边一个能变成你. 那么命中可以删除
                    dp[r][c] = dp[r - 1][c] + 1;
                }
                if (s1[r - 1] == s2[c - 1] && dp[r - 1][c - 1] != Integer.MAX_VALUE) {   // 如果我这个字符和你这个字符相等, 同时, 我前一个能变成你前一个. 那我就是前一个的解
                    dp[r][c] = Math.min(dp[r][c], dp[r - 1][c - 1]);
                }
            }
        }
        return dp[R - 1][C - 1];
    }

    // x字符串只通过删除的方式，变到y字符串
    // 返回至少要删几个字符
    // 如果变不成，返回Integer.Max
    public static int onlyDelete(char[] x, char[] y) {
        if (x.length < y.length) {
            return Integer.MAX_VALUE;
        }
        int N = x.length;
        int M = y.length;
        int[][] dp = new int[N + 1][M + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;
        // dp[i][j]表示前缀长度
        for (int i = 1; i <= N; i++) {
            dp[i][0] = i;
        }
        for (int xlen = 1; xlen <= N; xlen++) {
            for (int ylen = 1; ylen <= Math.min(M, xlen); ylen++) {
                if (dp[xlen - 1][ylen] != Integer.MAX_VALUE) {
                    dp[xlen][ylen] = dp[xlen - 1][ylen] + 1;
                }
                if (x[xlen - 1] == y[ylen - 1] && dp[xlen - 1][ylen - 1] != Integer.MAX_VALUE) {
                    dp[xlen][ylen] = Math.min(dp[xlen][ylen], dp[xlen - 1][ylen - 1]);
                }
            }
        }
        return dp[N][M];
    }

    // for test
    public static void main(String[] args) {
        char[] x = { 'a', 'b', 'c', 'd' };
        char[] y = { 'a', 'd' };

        System.out.println(onlyDelete(x, y));

        int str1Len = 20;
        int str2Len = 10;
        int v = 5;
        int testTime = 10000;
        boolean pass = true;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            String str1 = generateRandomString(str1Len, v);
            String str2 = generateRandomString(str2Len, v);
            int ans1 = minCost1(str1, str2);
            int ans2 = minCost2(str1, str2);
//            int ans3 = minCost3(str1, str2);
//            int ans4 = minCost4(str1, str2);
//            if (ans1 != ans2 || ans3 != ans4 || ans1 != ans3) {
            if (ans1 != ans2) {
                pass = false;
                System.out.println(str1);
                System.out.println(str2);
                System.out.println(ans1);
                System.out.println(ans2);
//                System.out.println(ans3);
//                System.out.println(ans4);
                break;
            }
        }
        System.out.println("test pass : " + pass);
    }

    public static String generateRandomString(int l, int v) {
        int len = (int) (Math.random() * l);
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            str[i] = (char) ('a' + (int) (Math.random() * v));
        }
        return String.valueOf(str);
    }


}
